package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.flag.knowledge.KLinkedList;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.List;

/**
 * 92。 翻转链表II
 * https://leetcode.cn/problems/reverse-linked-list-ii/
 *
 * head = [1,2,3,4,5], left = 2, right = 4
 * [1,4,3,2,5]
 */
@KLinkedList
public class LC92_ReverseLinkedListII {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
        Utils.printLinkedList(head);
        ListNode reversedHead = new Solution2().reverseBetween(head, 2, 4);
        Utils.printLinkedList(reversedHead);
    }

    /**
     *
     */
    static
    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummy = new ListNode(-1, head), prev = dummy;
            for (int i = 0; i < left - 1; i++) {
                prev = prev.next;
            }

            ListNode current = prev.next;
            for (int i = 0; i < right - left; i++) {
                ListNode next = current.next;
                current.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            return dummy.next;
        }
    }


    /**
     *
     */
    @XOptimal
    static
    class Solution1 {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummy = new ListNode(-1, head), p = dummy;
            for (int i = 0; i < left - 1; i++) {
                p = p.next;
            }

            ListNode prev = null, cur = p.next;
            for (int i = 0; i < right - left + 1; i++) {
                ListNode next = cur.next;
                // 核心
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            p.next.next = cur;
            p.next = prev;
            return dummy.next;
        }
    }


    static
    class Solution2 {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummy = new ListNode(-1, head), p = dummy;
            // 1 找翻转
            for(int i = 1; i < left; i++) {
                p = p.next;
            }

            // 2 局部替换
            ListNode current = p.next, prev = null;
            for(int i = 0; i < right - left + 1; i++) {
                ListNode next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }

            // 3 链接起来
            p.next.next = current;
            p.next = prev;
            return dummy.next;
        }
    }
}
